package com.azure.code.dfs;

import com.azure.code.tree.TreeNode;

/**
 * 路径总和I
 */
public class PathSum_112 {

    boolean found = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;

        backTrack(root,targetSum);
        return found;
    }
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        // base case
        if(root == null) return false;
        if(root.left==null&&root.right==null&& root.val == targetSum){
            return true;
        }
        return hasPathSum2(root.left,targetSum-root.val)
                || hasPathSum2(root.right,targetSum-root.val);
    }
    void backTrack(TreeNode root,int sum) {
        if(root==null) return;
        if(root.left==null&&root.right==null&&sum==root.val){
            found = true;
            return;
        }
        backTrack(root.left,sum-root.val);
        backTrack(root.right,sum-root.val);
    }
}
